package A一周刷爆LeetCode.A基础班.I暴力递归;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 打印全排列
 * @date 2022年04月15日 14:44
 */
public class Code03_PrintAllPermutations {

    public static List<String> permutation(String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        boolean[] boos = new boolean[str.length()];
        return process("", chars, boos);
    }

    private static List<String> process(String str, char[] chars, boolean[] boos) {
        if (str.length() == chars.length) {
            return Arrays.asList(str);
        }
        ArrayList<String> result = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            if (boos[i] || ((i != 0) && chars[i] == chars[i - 1] && !boos[i-1])) {
                continue;
            }
            boos[i] = true;
            List<String> list = process(str + chars[i], chars, boos);
            result.addAll(list);
            boos[i] = false;
        }
        return result;
    }

}
